Bellman Equation
V를 next(v)로 표현하기
V를 Q로 표현하기
\[\begin{aligned} v_{\pi}(s) &= \mathbb{E}[G_t|S_t = s]\\ &= \sum_{g_t}p(g_t|s)g_t \\ &= \sum_{g_t}\sum_{a}p(g_t,a|s)g_t\\ &= \sum_{g_t}\sum_{a}p(g_t|s,a)p(a|s)g_t\\ &= \sum_{a}p(a|s)\sum_{g_t}p(g_t|s,a)g_t \\ &= \sum_{a}Pr(A_t=a|S_t=s)\mathbb{E}[G_t|S_t=s,A_t=a] \\ &= \sum_{a}\pi(a|s)q_{\pi}(s,a) \end{aligned}\]Bellman Optimality Equation
Optimal state value function
\[\begin{aligned} v_{*}(s) = \underset{\pi}{\text{max}}\,v_{\pi}(s) , \forall s \in S \end{aligned}\]각각의 모든 state에서 모든 policy를 고려했을때 state-value function의 max값을 함숫값으로 가지는 함수이다. 이때 함숫값(max값)은 optimal policy에 의한 값이다.
Optimal state value function
\[\begin{aligned} q_{*}(s,a) = \underset{\pi}{\text{max}}\,q_{\pi}(s,a),\, \forall s \in S,\forall a \in A(s) \end{aligned}\]각각의 모든 state-action pair에서 모든 policy를 고려했을때 action-value function의 max값을 함숫값으로 가지는 함수. 이때 함숫값(max값)은 마찬가지로 optimal policy에 의한 값이다.
Optimal policy
- If \(v_{\pi}(s) \geq v_{\pi'}(s)\) for all \(s \in S\) then we say \(\pi\) is better than or equal to \(\pi'\).
- There is always at least one policy that is better than or equal to all othere policies => 다른 모든 정책들과 비교했을때 모든 state에서 value 같거나 더 나은 policy는 최소 한 개 이상 존재한다. 이러한 policy들을 모두 optimal policy라고 하며 \(\pi_*\) 로 표기한다.
- optimal policy는 여러개일 수 있다.
- optimal policy들은 모두 동일한 optimal state value function과 optimal action value function을 공유한다.
optimal policy \(\pi_*\)는 state-value function이 모든 s에서 다른 모든 policy들 보다 높거나 같은 값을 가지는 함수이다. 즉,다음과 같다.
state-value function은 action-value function으로 표현하는 Bellman equation에 의해 아래처럼 표현할 수 있었다.
\[\begin{aligned} v_{\pi}(s) &= \sum_{a}\pi(a|s)q_{\pi}(s,a)\\ &= \sum_{a}p(a|s)q_{\pi}(s,a) \end{aligned}\]\(v_{\pi}(s)\)를 maximize하는 policy는 어떻게 구해야 할까? 먼저 optimal action value function을 구했다고 가정해보자.(실제로 나중에 이를 추정하는 방법이 나온다.)
optimal action value function을 구했다는 것은 뭘까? optimal action value function은 agent가 어떤 state,action pair를 선택했을때 여러가지 policy를 다 고려해봐서 return(미래에 받을 reward의 총합)의 최댓값을 돌려준다. 즉, agent가 state에서 action을 선택했을 때 가장 많이 받을 수 있는 return이다.
예시를 들어보자. 임의의 state \(s\)에서 가능한 action의 집합을 \(A(s)= \{a_1,a_2,a_3,a_4\}\)이고 optimal action value function의 값이 다음과 같다고 하자.
\[\begin{aligned} &q_{*}(s,a_1) = 4 \\ &q_{*}(s,a_2) = -2 \\ &q_{*}(s,a_3) = 2 \\ &q_{*}(s,a_4) = 9 \\ \end{aligned}\]a1이라는 행동을 하면 가장 많이 return을 받아봤자 4이고 a2행동을 하면 가장 많이 받아봤자 return이 -2로 더 작을것이다. a4를 선택했을때에는 가장많이 받으면 return이 9이므로 a4를 s4에서의 action으로 취하면 가장 합리적일 것이다.
\(v_{\pi}(s)\)를 maximize하는 policy는 어떻게 구해야 할까? 먼저 state value function자체가 action value function부터 maximize가 되어 있어야 먼저 optimal action value function을 구했다고 가정해보자.(실제로 나중에 이를 추정하는 방법이 나온다.)
모든 \(\pi\)를 고려했을 때 위의 state-value function을 maximize하는 policy가 optimal policy였다. 다시쓰면 아래와 같다.
\[\pi_* = \underset{\pi}{\text{argmax}}\,v_{\pi}(s)\,,\forall s\]